{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Merge K Sorted Linked Lists\n",
    "\n",
    "[The Original Question](https://mp.weixin.qq.com/s/mFdazt8KSOxk_MAaMcPI-Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "You are given an array of k sorted singly linked lists. Merge the linked lists into a single sorted linked list and return it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, val, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "    def __str__(self):\n",
    "        c = self\n",
    "        answer = \"\"\n",
    "        while c:\n",
    "            answer += str(c.val) if c.val else \"\"\n",
    "            c = c.next\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(lists):\n",
    "    ascend = []\n",
    "    descend = []\n",
    "    for k in lists:\n",
    "        while k is not None:\n",
    "            if ascend != [] and k.val < ascend[-1]:\n",
    "                descend.append(ascend.pop())\n",
    "            elif descend != [] and descend[-1] < k.val:\n",
    "                ascend.append(descend.pop())\n",
    "            else:\n",
    "                ascend.append(k.val)\n",
    "                k = k.next\n",
    "    while descend != []:\n",
    "        ascend.append(descend.pop())\n",
    "    result = None\n",
    "    while ascend != []:\n",
    "        result = Node(ascend.pop(), result)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "123456\n"
     ]
    }
   ],
   "source": [
    "a = Node(1, Node(3, Node(5)))\n",
    "b = Node(2, Node(4, Node(6)))\n",
    "print(merge([a, b]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notes\n",
    "\n",
    "In the function `merge()`, there are 2 stacks - `ascend`, pushes elements from min to max, and `descend`, pushes elements from max to min. 2 stacks split the merged linked list into 2 parts and we can directly insert an element to one of these stacks' top.\n",
    "\n",
    "![Descriptions](37-1.png)\n",
    "\n",
    "Every time inserting an element into one of these 2 stacks, move the top element(s) from one to the other, keep inserting point between.\n",
    "\n",
    "After inserting all elements into these 2 stacks, pour `descend` elements into `ascend`. Cause *Python* only supports **Head insertion**, this operation make us easier to generate the merged linked list. When `ascend` becomes empty, all elements merged."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
